package q775_isIdealPermutation;

public class Solution_1 {
    /*
    全局倒置与局部倒置
    一个局部倒置一定是一个全局倒置
    因此要判断数组中局部倒置的数量是否与全局倒置的数量相等，只需要检查有没有非局部倒置就可以了。
    对于每一个 nums[i] 判断是否存在一个 j(j>i+1) 使得 nums[i]>nums[j] 即可。
    这和检查 nums[i]>min(nums[i+2],…,nums[n−1]) 是否成立是一致的
     */
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length, minSuff = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            if (nums[i] > minSuff) {
                return false;
            }
            minSuff = Math.min(minSuff, nums[i + 1]);
        }
        return true;
    }
}
